// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package bzip2

import "sort"

// huffmanTree是一个二叉树，它被一点一点地导航到
// 象征
type huffmanTree struct {
	// 节点包含树中的所有非叶节点。节点[0]是
	// 树的根和nextNode包含下一个元素的索引
	// 在构造树时要使用的节点数。
	nodes    []huffmanNode
	nextNode int
}

// huffmanNode是树中的节点。左侧和右侧将索引包含到
// 节点是树的一部分。如果left或right为invalidNodeValue，则该子项
// 是左节点，其值为leftValue/rightValue。
// None
// 这些符号是uint16s，因为bzip2在
// 树，但也有两个神奇的运行长度编码值和一个EOF符号。
// 因此，有超过256个可能的符号。
type huffmanNode struct {
	left, right           uint16
	leftValue, rightValue uint16
}

// invalidNodeValue是标记树中叶节点的无效索引。
const invalidNodeValue = 0xffff

// Decode从给定的位读取器读取位，并导航树，直到
// 找到了符号。
func (t *huffmanTree) Decode(br *bitReader) (v uint16) {
	nodeIndex := uint16(0) // 节点0是树的根。

	for {
		node := &t.nodes[nodeIndex]

		var bit uint16
		if br.bits > 0 {
			// 获得下一位-快速路径。
			br.bits--
			bit = uint16(br.n>>(br.bits&63)) & 1
		} else {
			// 获得下一位-慢路径。
			// 使用ReadBits检索单个位
			// 来自下属io.ByteReader。
			bit = uint16(br.ReadBits(1))
		}

		// 诱使编译器生成条件移动而不是分支，
		// 通过使两个负载都是无条件的。
		l, r := node.left, node.right

		if bit == 1 {
			nodeIndex = l
		} else {
			nodeIndex = r
		}

		if nodeIndex == invalidNodeValue {
			// 我们发现了一片叶子。使用位的值来决定
			// 是左值还是右值。
			l, r := node.leftValue, node.rightValue
			if bit == 1 {
				v = l
			} else {
				v = r
			}
			return
		}
	}
}

// newHuffmanTree从包含代码的片段构建Huffman树
// 每个符号的长度。最大代码长度为32位。
func newHuffmanTree(lengths []uint8) (huffmanTree, error) {
	// 有许多可能的树将相同的代码长度分配给
	// 每个符号（例如，考虑从中间倒出一棵树
	// 示例）。因为代码长度指定决定了
	// 这棵树的效率，每棵树都一样好。在里面
	// 以最小化构建树所需的信息量
	// bzip2使用规范树，以便在给定的
	// 只有代码长度指定。

	if len(lengths) < 2 {
		panic("newHuffmanTree: too few symbols")
	}

	var t huffmanTree

	// 首先，我们按代码长度升序对代码长度分配进行排序，
	// 使用符号值断开连接。
	pairs := make([]huffmanSymbolLengthPair, len(lengths))
	for i, length := range lengths {
		pairs[i].value = uint16(i)
		pairs[i].length = length
	}

	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i].length < pairs[j].length {
			return true
		}
		if pairs[i].length > pairs[j].length {
			return false
		}
		if pairs[i].value < pairs[j].value {
			return true
		}
		return false
	})

	// 现在我们将代码分配给符号，从最长的代码开始。
	// 我们在最重要的一端将代码打包到uint32中。
	// 因此，分支是从MSB向下获取的。这使我们很容易
	// 以后再分类。
	code := uint32(0)
	length := uint8(32)

	codes := make([]huffmanCode, len(lengths))
	for i := len(pairs) - 1; i >= 0; i-- {
		if length > pairs[i].length {
			length = pairs[i].length
		}
		codes[i].code = code
		codes[i].codeLen = length
		codes[i].value = pairs[i].value
		// 我们需要“增加”代码，这意味着处理|代码|
		// 就像一个|长度|位数字。
		code += 1 << (32 - length)
	}

	// 现在我们可以按代码排序，这样每个分支的左半部分
	// 递归地分组在一起。
	sort.Slice(codes, func(i, j int) bool {
		return codes[i].code < codes[j].code
	})

	t.nodes = make([]huffmanNode, len(codes))
	_, err := buildHuffmanNode(&t, codes, 0)
	return t, err
}

// huffmanSymbolLengthPair包含一个符号及其代码长度。
type huffmanSymbolLengthPair struct {
	value  uint16
	length uint8
}

// huffmanCode包含一个符号、其代码和代码长度。
type huffmanCode struct {
	code    uint32
	codeLen uint8
	value   uint16
}

// buildHuffmanNode获取已排序的huffmanCodes片段，并在中构建一个节点
// 给定级别的哈夫曼树。它返回新的索引
// 构造节点。
func buildHuffmanNode(t *huffmanTree, codes []huffmanCode, level uint32) (nodeIndex uint16, err error) {
	test := uint32(1) << (31 - level)

	// 我们必须搜索代码列表以找到左右两侧之间的区别。
	firstRightIndex := len(codes)
	for i, code := range codes {
		if code.code&test != 0 {
			firstRightIndex = i
			break
		}
	}

	left := codes[:firstRightIndex]
	right := codes[firstRightIndex:]

	if len(left) == 0 || len(right) == 0 {
		// 哈夫曼树中有一个多余的级别
		// 编码器中的错误。但是，在中已观察到此错误
		// 野生动物，所以我们处理它。

		// 如果这个函数是递归调用的，那么我们知道
		// len（codes）>=2，否则，我们会遇到
		// “叶节点”的情况下，下面，而不是递归。
		// None
		// 但是，对于初始调用，可能是len（代码）
		// 是零还是一。这两种情况都无效，因为长度为零
		// 树不能编码任何内容，长度为1的树只能
		// 编码EOF，因此是多余的。我们拒绝两者。
		if len(codes) < 2 {
			return 0, StructuralError("empty Huffman tree")
		}

		// 在这种情况下，递归并不总是减少长度
		// 所以我们需要确保通过另一个
		// 机械装置
		if level == 31 {
			// 由于len（codes）>=2，值
			// 如果32位相等，则可以匹配所有32位
			// 这是无效的。这确保了我们永远不会进入
			// 无限递归。
			return 0, StructuralError("equal symbols in Huffman tree")
		}

		if len(left) == 0 {
			return buildHuffmanNode(t, right, level+1)
		}
		return buildHuffmanNode(t, left, level+1)
	}

	nodeIndex = uint16(t.nextNode)
	node := &t.nodes[t.nextNode]
	t.nextNode++

	if len(left) == 1 {
		// 叶节
		node.left = invalidNodeValue
		node.leftValue = left[0].value
	} else {
		node.left, err = buildHuffmanNode(t, left, level+1)
	}

	if err != nil {
		return
	}

	if len(right) == 1 {
		// 叶节
		node.right = invalidNodeValue
		node.rightValue = right[0].value
	} else {
		node.right, err = buildHuffmanNode(t, right, level+1)
	}

	return
}
